选数

题目 选数

image-d24fe65e

思路分析

求组合数 如果不剪枝的话 其实就和前面的全排列差不多

甚至还不需要标记某个数用没用过 因为后一个数必须比前一个数大 所以一定不会被用过

这题就是先做出组合数 然后判断是否为素数（试除法）

代码实现

#include<bits/stdc++.h>
using namespace std;

const int N=25;
int a[N];
int way[N];
int n,k;
int res;

bool is_prime(int x){
	if(x<2) return false;
	for(int i=2;i<=x/i;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
}

void dfs(int u,int start){
	if(u==k+1){
		int sum=0;
		for(int i=1;i<=k;i++){
			sum+=way[i];
		}
		if(is_prime(sum))
			res++;
		return;
	}

	for(int i=start;i<=n;i++){
		way[u]=a[i];
		dfs(u+1,i+1);
		way[u]=0;
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	dfs(1,1);
	cout<<res;
	return 0;
 }

#include<bits/stdc++.h>
using namespace std;

const int N=25;
int a[N];
int way[N];
int n,k;
int res;

bool is_prime(int x){
	if(x<2) return false;
	for(int i=2;i<=x/i;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
}

void dfs(int u,int start){
    if(u+n-start<k) //剪枝(后续位置不够放)
        return;

	if(u==k+1){
		int sum=0;
		for(int i=1;i<=k;i++){
			sum+=way[i];
		}
		if(is_prime(sum))
			res++;
		return;
	}

	for(int i=start;i<=n;i++){
		way[u]=a[i];
		dfs(u+1,i+1);
		way[u]=0;
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dfs(1,1);
	cout<<res;
	return 0;
 }

同类题型

视频讲解

⬅️ 组合数 🏠 00-刷题理模型 ➡️ 转载